package BST;

public class ArvoreBinaria {

	private No raiz;
   
	/**
	 * Insere um elemento na arvore
	 * 
	 * @param elemento  a ser inserido
	 * 
	 * @return o nodo inserido 
	 *         ou null caso o nodo ja exista na arvore
	 *         
	 *         ESQUERDA < menores
	 *         DIREITA  > MAIORES
	 */
	public No insere(int elemento) {		
		
		if(procura(elemento) != null)
			return null;
		
		
		No noInserido = new No(elemento);
		
		No nodoTempPai = null;
		No nodoTemp = raiz;
		
		while (nodoTemp != null) {
			
			nodoTempPai = nodoTemp;
			
			if (noInserido.getElemento() < nodoTemp.getElemento())
				nodoTemp = nodoTemp.getEsquerda();
			
			else
				nodoTemp = nodoTemp.getDireita();
		}
		
		noInserido.setAntecessor(nodoTempPai);
		
		if (nodoTempPai == null)
			raiz = noInserido;
		
		else if (noInserido.getElemento() < nodoTempPai.getElemento())
			nodoTempPai.setEsquerda(noInserido);
		
		else
			nodoTempPai.setDireita(noInserido);
		
		return noInserido;
	}
	
	
	/**
	 * Remove e retorna um no da arvore
	 * 
	 * @param no a ser removido
	 * @return o no removido 
	 *         null caso o no nao exista
	 * 
	 */
	public No remove(int elemento) {
				
		// procura se o no esta na arvora
		No z = procura(elemento);
		
		// retorna null caso nao encontre o no
		if(z == null)
			return null;
		
		No y = null;
		No x = null;
		
		// determina o no y que vai ser extraido
		if (z.getEsquerda() == null || z.getDireita() == null)
			y = z;
		else
			y = sucessor(z);
		
		// x eh defenido como filho de y ou null caso y nao tenha filhos
		if (y.getEsquerda() != null) 
			x = y.getEsquerda();
		else 
			x = y.getDireita();
		
		// ocorre a extracao de y, procura casos extremos como extracao da raiz e quando nao tem filhos
		if (x != null)
			x.setAntecessor(y.getAntecessor());
		if (y.getAntecessor() == null)
			raiz = x;
		else if (y.getElemento() <= y.getAntecessor().getElemento())
			y.getAntecessor().setEsquerda(x);
		else
			y.getAntecessor().setDireita(x);
		
		// se o sucessor de z foi o no extraido, passa os dados satelites de y para z	
		if (y.getElemento() != z.getElemento())
			z.setElemento(y.getElemento());
		return y;
	}

	
	/**
	 * Pesquisa e retorna o no sucessor de um dado no
	 * 
	 * @param no
	 *            a ser avaliado
	 * @return o sucessor de um dado no
	 */
	private No sucessor(No no) {
		if (no.getDireita() != null)
			return minimo(no.getDireita());
		No noTempPai = no.getAntecessor();
		while (noTempPai != null
				&& no.getElemento() > noTempPai.getElemento()) {
			no = noTempPai;
			noTempPai = noTempPai.getAntecessor();
		}
		return noTempPai;
	}

	/**
	 * Retorna o menor filho em pesquisa up-down a partir de um no
	 * 
	 * @param no
	 *            a ser avaliado
	 * @return o menor filho em pesquisa up-down a partir de um no
	 */
	private No minimo(No no) {
		while (no.getEsquerda() != null)
			no = no.getEsquerda();
		return no;
	}

	/**
	 * Pesquisa um no da arvore binaria de pesquisa
	 * @param no a ser pesquisado
	 * @return o no pesquisado,  
	 *         ou null caso o elemento nao exista
	 */
	public No procura(int elemento) {
		No raizTemp = raiz;		

		while (raizTemp != null
				&& raizTemp.getElemento() != elemento) {
			
			if (elemento < raizTemp.getElemento())
				raizTemp = raizTemp.getEsquerda();
			else
				raizTemp = raizTemp.getDireita();
		}
		

		return raizTemp;
	}

	/**
	 * Retorna uma string representando a ?rvore percorrida emOrdem.
	 * 
	 * Caso a ?rvores esteja vazia, deve ser retornado a string "" (vazia)
	 * 
	 * @return A string com os valores dos nodos da ?rvore ordenados (crescente)
	 */
	public String percorreEmOrdem() {
		if (raiz == null)
			return "";
		return caminhaEmOrdem(raiz, "");
	}

	/**
	 * Realiza o caminhamento pre ordem na arvora
	 * 
	 * @param no
	 *            a ser caminhado
	 * @param s
	 *            resultado do caminhamento
	 */
	private String caminhaEmOrdem(No no, String s) {
		if (no != null) {
            
			s = caminhaEmOrdem(no.getDireita(), s);
			s += " " + no.getElemento() ;
			s = caminhaEmOrdem(no.getEsquerda(), s);
			
		}
		return s.trim();
	}

	
	/**
	 * Retorna a raiz da arvore bin�ria
	 * 
	 * @return a raiz da arvore bin�ria
	 */
	public No getRaiz() {
		return raiz;
	}

	/**
	 * Modifica a raiz da arvore Binaria
	 * 
	 * @param raiz
	 *            a ser modificada
	 */
	public void setRaiz(No raiz) {
		this.raiz = raiz;
	}
	
	
	/**
	 * Retorna o tamanho da arvore
	 * @return o tamanho da arvore
	 */
	public int getTamanho(){
		return getTamanho(raiz);
	}
	
	/**
	 * Retorna o tamanho da arvore
	 * @param raiz a raiz da arvore
	 * @return o tamanho da arvore
	 */
	private int getTamanho(No raiz){
		if(raiz == null)
			return 0;		
		return getTamanho(raiz.getEsquerda())+getTamanho(raiz.getDireita())+1;
	}
	
}